This invention relates to topology and geometry compression and coding schemes used in interactively creating, manipulating and transmitting 3-D geometry, especially through remote networked environments.
Demand for 3-D imagery in entertainment, advertising, education, medicine, CAD, architecture and elsewhere, is high and increasing. As a result, there is a growing need for more efficient rendering of scanned images of 3-D objects; and more error-resistant transmission and reception of these through error-prone internet, broadcast, and wireless networks to a remote location.
Digital representations of stationary 3-D objects typically consist of large numbers of discrete polygons, encoded by various methods to reflect location, geometric, connectivity, texture, and other surface characteristics. One of the promising current modeling processes involves the use of surface models made up of triangles. Much research for this model has centered on geometry data compression, and incremental and progressive streaming modes of geometric model transmission. An ongoing challenge is to design efficient data structures that encompass both the compactness of a geometric compression scheme and the superior visual quality of a progressive representation.
In an error-prone communication environment, however, it is necessary to also have a more robust mechanism over an unreliable network because data packets may be corrupted or lost. Once an error occurs, quick recovery should be promptly processed for direct interaction with the remote 3-D data set. The decoder must be able to synchronize and continue decoding the received stream instead of requiring retransmission from scratch. To transmit large compressed 3-D data, it is therefore desirable that the encoded bit stream also supports incremental transmission. That is, the receiving party should be able to decode and display whatever information it has received from the server without retransmission.
The fundamental idea in progressive transmission is that most important information of an object is sent first, followed by a series of details. The most important information forms an object at the coarsest level of resolution. The details are used to successively update the coarsest and intermediate meshes. The advantages that progressive transmission offers are numerous: high performance, embedded bit stream which can be truncated at any point by the decoder to create the best corresponding reconstructed 3-D object and exact bit rate control.
Another efficiency currently being applied in the digital representation of 3-D objects is mirroring. Mirroring is the taking advantage of left-right mirror symmetries such as are exhibited in faces/heads and body segments, biological organisms and structures, vehicles, machine parts, and furniture. Mirroring can substantially reduce the amount of data needed to reproduce an image, by transmitting a left-image and then for the right image, only information as to slight asymmetries. The utility of mirroring, however, is in part dependent on availability of an efficient coding, transmission and decoding of the slight asymmetries.
Several teachings in the prior art directed generally to efficient coding, transmission and decoding of 3-D images are noteworthy. One process described in xe2x80x9cArbitrary Topology Shape Reconstruction from Planar Cross Sectionsxe2x80x9d, Bajaj et. al.; Graphical Models and Image Procession, 58, 6 (1996), 524-543, is to represent polygonal mesh connectivity as generalized triangle strips, and to compactly express a planar graph via stack operators such that the total number of random accesses to all vertices of the mesh is greatly reduced. Linear predictions are used to quantize and code the vertex positions and attributes. The compression ratio is usually not high, however.
The Topological Surgery (TS) method described in xe2x80x9cOptimized Geometry Compression for Real Time Renderingxe2x80x9d, Chow, M. M., Proceedings of IEEE Visualization ""97, 347-354, is a compression scheme over a set of manifold triangular meshes. TS organizes vertices of a mesh into a vertex spanning tree and triangles into simple polygons which are further grouped to a series of triangle strips. Vertex positions are predicted by linear combinations of the encoded positions of their ancestors in the vertex spanning tree. Geometry and connectivity encoding can be processed separately. The advantage of this scheme lies in its connectivity efficiency, about 2-3 bits per triangle. However, this scheme cannot handle non-manifold meshes directly; and currently it is difficult to design hardware supported decompression algorithms for it, because the random access nature of TS takes up too much bus bandwidth.
In xe2x80x9cGeometric Compressionxe2x80x9d, Deering, M., Computer Graphics (Proc. SIGGRAPH) (1995), 13-20, a further process is noted for decomposing a given mesh into several generalized triangular meshes, as well as a geometry and topology encoding scheme. While optimized for real-time rendering, the process is not compression-efficient.
Most existing compression methods only work correctly on manifold meshes or meshes of even more narrowed classes. To compress a non-manifold polygonal mesh, most methods need to convert it into a manifold mesh in a preprocessing step. In the article xe2x80x9cVector Quantization and Signal Compressionxe2x80x9d, Gersho et. al.; Norwell, M A: Kluwer Academic Publishers, 1992, such a conversion process works by cutting-and-stitching operations over singular vertices and edges. However, since cutting-and-stitching operations ignore vertex coordinates, there may exist two connected components in the resulted manifold mesh that have coincident boundaries. The crack problem arises when positions of coincident vertices are quantized using different predictions.
The article xe2x80x9cVector Quantizationxe2x80x9d, Grey, R. M. IEEE ASSP Magazine I, 2 (1984), 4-29, describes a mesh with recursive subdivision connectivity to approximate a mesh of arbitrary topology. Wavelets are introduced to do multiresolution analysis of meshes with such connectivity property. Hierarchical quaternary subdivision trees are used to organize the vertices which will be coded in a top-down mode. Prediction coding is used for vertex positions by means of surface fitting. This wavelet-based scheme does not, however, support lossless compression because most meshes do not have subdivision connectivity.
Another scheme suggested in Handbook of Visual Communications, Hang et. al. Academic Press, 1995 is the adaptive-refinement Progressive Mesh (PM). It stores a manifold mesh as a low resolution coarse mesh together with an ordered sequence of details that can be used to refine the coarse mesh. Edge collapse and vertex split are two basic operations. Each vertex split operation adds a new vertex and two new triangles and locally refines the coarse mesh. This method, however, also is not compression-efficient.
In the article xe2x80x9cView-Dependent Refinement of Progressive Meshesxe2x80x9d, Hoppe, H., Computer Graphics (Proc SIGGRAPHS) (1997), 189-198, . . . , a lossy connectivity compression technique is described which outputs a progressively transmittable bit stream. The original simplicial mesh at different resolutions is expressed through successive edge collapse and merging operations, a scheme described in xe2x80x9cA Method for the Construction of Minimum-redundancy Codesxe2x80x9d Hufffnan, D. A., Proceedings of the IRE 40 (1952) 1098-1101. While not being an efficient coding method, its fundamental contribution is its support for the progressive transmission. The method is slightly improved by an idea provided in [xe2x80x9cView-dependent Simplification of Arbitrary Polygonal Environmentsxe2x80x9d Luebke et. al., Computer Graphics (Proc SIGGRAPH ""97) (1997), 199-208, by integrating the structured bit stream and the attribute stream under certain optimized criteria.
Progressive Forest Split (PFS) described in Progressive Compression of 3-D Models, IEEE Proceedings of Multimedia Computing and Systems (Ottowa Canada, 1997), is a compact representation for any manifold mesh. PFS decomposes a given mesh by a low resolution level-of-detail and a sequence of forest split operations. The forest split operation is specified by a forest in the graph of vertices and edges of the mesh, a sequence of simple polygons, and a sequence of vertex displacements. In order to express each forest split operation, forest edges, sequence of simple polygons, and vertex displacements are coded into compressed data stream.
An approach for constructing smooth parameterizations of irregular connectivity triangulation of genus 2-manifolds, is described in xe2x80x9cHierarchical Structures for Dynamic Polygonal Simplificationxe2x80x9d Luebke, D., Tech Rep. TR 96-006, Dept. of Computer Science, Univ. of N. Carolina Chapel Hill, 1996. A hierarchical simplification technique is used so that a parameterization of the original mesh over a coarse base mesh is obtained. To get an approximation with a specified error bound, the base mesh is hierarchically subdivided by the Loop method described in xe2x80x9cSurfaces from Contoursxe2x80x9d, Meyers et. al., ACM Trans. On Graphics, II, 3(1992), 228-258. This multiresolution adaptive parameterization and remeshing technique can be used for progressive transmission of polygonal meshes in applications that do not require perfect connectivity recovery.
An improved topological layering scheme coupled with vector quantization provides in accordance with the invention a unique combination of compressing and encoding of both the topology (connectivity) and geometry (vertex coordinates) of arbitrary polygon meshes. The separation of topology and geometry encoding permits all combinations of lossy and lossless topology, as well as lossy or lossless geometry.
In the encoding scheme, a given mesh is first decomposed into contours. Then contours are constructed for each vertex contour and triangle strips and fans for each triangle contour. The multiresolution surfaces are constructed in two phases. The first phase requires two operations: intra-contour simplification and inter-contour simplification. The second phase provides flexible resolution degree and may change the mesh topology while the details are still expressed in some economical way. The contour construction uses a closed sequences of edges. The geometric primitives for the two basic kinds of contours, vertex and triangle, are encoded independently and alternately.
In a specific illustrative embodiment, connectivity information is expressed by defining a novel kind of triangle strip, created by an existing layered decomposition method. All vertices are grouped into separate layers; and each vertex layer is further divided into a set of contours and possibly some isolated vertices. A xe2x80x9cgeneralizedxe2x80x9d triangle strip is the basic geometric primitive, and represents the set of triangles that lie between two adjacent vertex layers. Large numbers of long generalized triangle strips are developed. The invention teaches, in addition, using an exception strip, so-named because triangles are present therein which have xe2x80x9cbubblesxe2x80x9d, that is, triangles for which all three vertices lie in the parent vertex layer; and in addition non-triangles or xe2x80x9cholesxe2x80x9d. To encode a strip, whether exceptional or not, the process identifies the two starting vertices by a local index; the bit march, including length; and bubbles (including the number of bubbles) by both local and relative index. Contained in this information is all of the connectivity encoding needed for the far-end decoder to recover the original triangle strip.
Geometry encoding is improved by a novel productive vector quantization scheme which efficiently encodes vector coordinates of a given meshed object. In order to encode without accumulating error, the deviation of any vertex position is controlled to within the distortion of the productive vector quantization. The key is that once a correction vector is quantized, its distortion is merged into its following correction vector.
Progressive connectivity transmission is achieved by using both intra-layer decomposition and reconstruction; and inter-layer decomposition and reconstruction. The inter-layer transmission scheme eliminates having to encode a whole vertex layer.
The progressive geometry encoding uses a process of encoding vertices at the lowest level by a code difference approach. As resolution level increases, the prediction points for new vertices are first computed; and their corresponding correction vectors are then encoded by conventional PVQ techniques.
In a particular implementation, an improved mirroring process uses a geometry delta layer which specifies delta values to vertex positions of the mirrored or copied object. The delta values may be coded and transmitted in accordance with the techniques described.
As applied to the sending of 3-D images through a network, topology and geometry data obtained from a scanning of an object are encoded and a bit stream is created for progressive transmission in accordance with the teachings. The bit stream is transmitted through the network to a remote station where a decoder interprets and reconstitutes the encoded data. An image of the object is displayed on a monitor.
The advantages of these process innovations over prior methods, are their capability for handling arbitrary polygon meshes (high genus, non-manifold) and achieving higher compression ratios, while allowing for progressive transmission of the encoded geometry with error/distortion control parameters. These and other aspects, features and advantages of the invention are more fully elucidated below in an illustrative embodiment practiced in a network environment.